#ifndef BPLUS_TREE_H
#define BPLUS_TREE_H

#include <fstream>
#include <vector>

// 节点大小（4KB）
const int PAGE_SIZE = 4096;
// 最大键数
const int MAX_KEYS = (PAGE_SIZE - sizeof(bool) - sizeof(int) * 2 - sizeof(long long)) 
                     / (sizeof(int) + sizeof(long long));

struct BPlusTreeNode {
    // 是否为叶子节点
    bool is_leaf;
    // 当前键数量
    int key_count;
    // 键（id）
    int keys[MAX_KEYS];
    // 子节点偏移/数据偏移
    long long children[MAX_KEYS + 1];
    // 叶子节点的下一个叶子偏移
    long long next_leaf;

    BPlusTreeNode() : is_leaf(false), key_count(0), next_leaf(-1) {}
};

class BPlusTree {
public:
    explicit BPlusTree(const std::string& index_filename);
    ~BPlusTree();

    // 插入键值对(id, 数据偏移)
    void insert(int key, long long data_offset);
    // 删除id
    bool remove(int key);
    // 查找id对应的偏移
    bool find(int key, long long& data_offset);
    // 范围查询[start, end)，先锁定start然后在叶子结点中顺序查找，如果一个叶子结束直接找到下一个叶子，直到找到end结束
    std::vector<long long> range_query(int start, int end);
    // 获取根节点偏移
    long long get_root() const { return root; }
    // 供外部读取节点
    void read_node(long long offset, BPlusTreeNode& node);

private:
    // 索引文件流
    std::fstream index_file;
    // 根节点偏移
    long long root;
    // 最小键数（MAX_KEYS/2）
    int min_keys;

    // 将结点写入索引文件偏移为offset的地方
    void write_node(long long offset, const BPlusTreeNode& node);
    // 分配新节点并返回新结点在索引文件中的偏移
    long long allocate_new_node();

    // 插入相关
    // 叶子结点满进行分裂
    void split_leaf(BPlusTreeNode& leaf, long long leaf_offset);
    // 非叶子结点满进行分裂
    void split_internal(BPlusTreeNode& internal, long long internal_offset);
    // 插入到某个叶子结点中
    void insert_into_leaf(BPlusTreeNode& leaf, int key, long long data_offset);
    // 插入到某个非叶子结点中
    void insert_into_internal(BPlusTreeNode& parent, int key, long long left, long long right);
    //递归从根节点开始向叶子结点插入(key,data_offset)键值对
    bool insert_recursive(long long node_offset, int key, long long data_offset, int& promoted_key, long long& promoted_node);

    // 删除相关
    //合并叶子结点
    void merge_leaf(BPlusTreeNode& left, BPlusTreeNode& right, long long left_offset, long long right_offset);
    //合并非叶子结点
    void merge_internal(BPlusTreeNode& left, BPlusTreeNode& right, long long left_offset, long long right_offset, int key);
    // 若删除后结点数不够，向左边结点借一个结点
    void redistribute_leaf(BPlusTreeNode& left, BPlusTreeNode& right, long long left_offset, long long right_offset);
    // 若删除后结点数不够，向左边结点借一个结点
    void redistribute_internal(BPlusTreeNode& left, BPlusTreeNode& right, long long left_offset, long long right_offset);
    //从叶子结点删除一个数据
    bool remove_from_leaf(BPlusTreeNode& leaf, long long leaf_offset, int key);
    //从根节点开始递归搜索到叶子并删除
    bool remove_recursive(long long node_offset, int key);
};

#endif // BPLUS_TREE_H